import java.util.Arrays;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[0]);

        for (int i = 0; i < inorder.length; i++) {
            //此时两种遍历均遍历完左部分
            if (inorder[i] == root.val) {
                int[] pre_left = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] pre_right = Arrays.copyOfRange(preorder, i + 1, preorder.length);

                int[] in_left = Arrays.copyOfRange(inorder, 0, i);
                int[] in_right = Arrays.copyOfRange(inorder, i + 1, inorder.length);

                //想象子树是新树
                root.left = buildTree(pre_left, in_left);
                root.right = buildTree(pre_right, in_right);

                break;
            }
        }

        return root;
    }
}

public class CreateBinaryTreeByTraversal {
    public static void main(String[] args) {
        // 示例输入
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};

        // 创建Solution实例
        Solution solution = new Solution();

        // 构建二叉树
        TreeNode root = solution.buildTree(preorder, inorder);

        // 验证结果
        System.out.println("构建完成，根节点值为: " + root.val);
        System.out.println("左子节点值为: " + (root.left != null ? root.left.val : "null"));
        System.out.println("右子节点值为: " + (root.right != null ? root.right.val : "null"));
    }
}